package com.zhangxiaofanfan.hotcode.second;

/**
 * <a href="https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked">200. 岛屿数量</a>
 *
 * @author zhangxiaofanfan
 * @date 2024-06-26 20:33:33
 */
public class HotCode051 {
    public static void main(String[] args) {
        char[][] grid = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        HotCode051 hotCode = new HotCode051();
        System.out.println(hotCode.numIslands(grid));
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int landCount = 0, row = grid.length, col = grid[0].length, rowIndex, colIndex;
        boolean[][] map = new boolean[row][col];
        for (rowIndex = 0; rowIndex < row; rowIndex++) {
            for (colIndex = 0; colIndex < col; colIndex++) {
                if (grid[rowIndex][colIndex] == '1' && !map[rowIndex][colIndex]) {
                    bfs(grid, map, rowIndex, colIndex);
                    landCount++;
                }
            }
        }
        return landCount;
    }

    public void bfs(char[][] grid, boolean[][] map, int row, int col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || map[row][col] || grid[row][col] == '0') {
            return;
        }
        map[row][col] = true;
        bfs(grid, map, row + 1, col);
        bfs(grid, map, row - 1, col);
        bfs(grid, map, row, col + 1);
        bfs(grid, map, row, col - 1);
    }
}
